#pragma once

#include <iostream>
#include <algorithm>
class KthSearch {
public:
	/* 获取两个排序数组中的第k小的数， 时间复杂度为O(log(m+n)) */
	int getKth(int arr1[], int start1, int end1, int arr2[], int start2, int end2, int k) {
		int len1 = end1 - start1 + 1;
		int len2 = end2 - start2 + 1;

		//确保arr1的长度小于arr2的长度
		if (len1 > len2) {
			return getKth(arr2, start2, end2, arr1, start1, end1, k);
		}
		//长度最先到0的数组肯定是arr1
		if (len1 == 0) {
			return arr2[start2 + k - 1];
		}
		if (k == 1) {
			return std::min(arr1[start1], arr2[start2]);
		}
		//二分查找,每次去掉k/2个数据
		int i = start1 + std::min(k / 2, len1) - 1;
		int j = start2 + std::min(k / 2, len2) - 1;
		if (arr1[i] > arr2[j]) {//将小的那一半数据截去不要，然后再递归查找
			return getKth(arr1, start1, end1, arr2, j + 1, end2, k - (j - start2 + 1));
		} else {
			return getKth(arr1, i + 1, end1, arr2, start2, end2, k - (i - start1 + 1));
		}
	}
};